
// ================ Start of Helper Function Definitions ================ //

// Given a row number, it returns home row of the box
// Given a col number, it returns home col of the box
// Given a box number, it returns home row of the box (Due to transpose property of Sudoku)
// NOTE: Optimization concerns
//       Out of the possible implementations (switch, Math.floor, and modulo), modulo and switch appear to be the faster ones. 
//       Modulo was chosen because it is faster on IE.
function CalcBoxHomeCell(num)
{
	return num - (num % 3);
	// return Math.floor(num / 3) * 3;
}

// Given a cell position in row/col, it returns the box number of that cell
// Given a cell position in box/pos, it returns the row number of that cell (Due to transpose property of Sudoku)
function CalcBoxNum(r, c)
{
	// Note that in modulo calculation, floating point rounding error should be considered.
	return (c - c % 3) / 3 + r - r % 3;
	// return Math.floor(r / 3) * 3 + Math.floor(c / 3);
}

// Array.prototype.map style function, takes callback function as parameter.
// Loop a non-returning callback function through all cells sharing a row/col/box with the given cell.
function CallPeers(row, col, func, arg)
{
	for (var i = 0; i < 9; i++)
	{
		if (col !== i) func(row, i, arg);
		if (row !== i) func(i, col, arg);
	}

	var HomeRow = CalcBoxHomeCell(row);
	var HomeCol = CalcBoxHomeCell(col);

	for (var r = HomeRow; r < HomeRow + 3; r++)
		for (var c = HomeCol; c < HomeCol + 3; c++)
			if ((r !== row) && (c !== col))
				func(r, c, arg);
}

// ================ Start of Sudoku Grid Definitions ================= //


// Sudoku object contains data for a grid
// Each instance contains a data grid and a notation grid.
function SudokuGrid(parameter)
{
	// preventive - when user attempts to change the value of a non-clue cell, the value must be valid.
	// assertive - when user change the value of a non-clue cell, immediate conflicts are resolved assuming the new entry is valid. 
	// none - user can change non-clue cells freely.
	this.enforcement = 'preventive'; // preventive, assertive, none

	this.notations = []; // bitmask of candidates of the cell.
	this.data = []; // bitmask of the cell's value.

	this.dataCount = 0;

	// if the parameter is another sudoku grid, we would copy it
	if (parameter && parameter.data && parameter.notations)
	{
		for (var i = 0; i < 9; i++)
		{
			// slice returns a section of an array as new array
			this.notations[i] = parameter.notations[i].slice(0); 
			this.data[i] = parameter.data[i].slice(0); 
		}
		this.enforcement = parameter.enforcement;
		this.dataCount = parameter.dataCount;
	}
	else
	{
		for (var i = 0; i < 9; i++)
		{
			this.data[i] = [0, 0, 0, 0, 0, 0, 0, 0, 0];
			this.notations[i] = [511, 511, 511, 511, 511, 511, 511, 511, 511];
		}
		
		// If the paramter is a string, attempts to load it, nothing will happen if it fails. 
		if (parameter && typeof(parameter) === 'string')
		{
			this.loadFromString(parameter);
		}
	}
}

SudokuGrid.prototype = 
{
	// these functions returns the missing values (i.e. cell's candidates) in the respective row/col/box/cell.
	tallyRow : function (row)
	{
		var mask = 511;
		for (var c = 0; c < 9; c++)
			mask &= ~this.data[row][c];
		return mask;
	},

	tallyCol : function (col)
	{
		var mask = 511;
		for (var r = 0; r < 9; r++)
			mask &= ~this.data[r][col];
		return mask;
	},

	tallyBox : function (box)
	{
		var mask = 511;
		var HomeRow = CalcBoxHomeCell(box);
		var HomeCol = (box % 3) * 3;

		// loop thru box
		for (r = HomeRow; r < HomeRow + 3; r++)
			for (c = HomeCol; c < HomeCol + 3; c++)
				mask &= ~this.data[r][c];

		return mask;
	},

	// Returns the candidate list for a cell, the list could include or exlude the cell itself
	tallyCandidates : function (row, col, includeSelf)
	{
		var refObj = { t : 511 };
		var func = function (grid, obj) { return function (r, c) { obj.t &= ~grid.data[r][c]; } }(this, refObj);
		CallPeers(row, col, func);

		if (includeSelf)
			return refObj.t | this.data[row][col];
		else
			return refObj.t;
	},

	// check if a cell is empty
	isEmpty : function (row, col)
	{
		return (this.data[row][col] === 0);
	},

	// getter using human readable digit
	getDigit : function (r, c)
	{
		// console.log('Getting cell digit: (' + r + ', ' + c + ')');
		return this.data[r][c].bitmaskToDigit();
	},

	// setter using human readable digit
	setDigit : function (r, c, digit)
	{
		var bitvalue = digit.digitToBitmask();

		if (this.enforcement === 'preventive')
		{
			if (bitvalue !== 0 && (this.tallyCandidates(r, c, true) & bitvalue) === 0) return false;
		}
		else if (this.enforcement === 'assertive')
		{
			this.assertDigit(r, c, ~bitvalue);
		}

		//console.log('Modifying cell: (' + r + ', ' + c + ') to ' + bitvalue);
		this.setDigitByBitvalue(r, c, bitvalue);
		return true;
	},

	// bitwise setter
	// !!! THIS FUNCTION MUST BE USED TO SET VALUE !!! It keeps track of the dataCount tallies
	setDigitByBitvalue : function (r, c, bitvalue)
	{
		// modify data count
		if (this.isEmpty(r, c))
		{
			if (bitvalue !== 0) this.dataCount++;
		}
		else
		{
			if (bitvalue === 0) this.dataCount--;
		}

		// set value
		this.data[r][c] = bitvalue;
	},

	// Enforcement functions
	// clears all immediately conflicting value
	assertDigit : function (row, col, mask)
	{
		var func = function (grid, m){ return function (r, c, m) { grid.data[r][c] &= ~m; } } (this, mask);
		CallPeers (row, col, func);
	},

	// Getter and setter for the notations. 
	// These functions deals in bitmask. 
	getNotation : function (r, c)
	{
		return this.notations[r][c];
	},

	setNotation : function (r, c, bitvalue)
	{
		this.notations[r][c] = bitvalue;
	},

	// get bit value using box reference
	getNotationBox : function (box, pos)
	{
		var row = CalcBoxNum(box, pos);
		var col = (box % 3) * 3 + (pos % 3);
		return this.notations[row][col];
	},

	// set bit value using box reference
	setNotationBox : function (box, pos, bitvalue)
	{
		var row = CalcBoxNum(box, pos);
		var col = (box % 3) * 3 + (pos % 3);
		this.notations[row][col] = bitvalue;
	},

	// Cross-sectional setter and getter
	// Used by certain solving techniques, especially the "subset" group.
	// Used in setting and unsetting of masks to a whole row/column/box.

	// returns a position mask of the value's presence in the row. Least significant bit is cell 0.
	getPositionsInRow : function (bitvalue, row)
	{
		var positions = 0; // variable to return

		// loop thru columns
		for (var c = 0; c < 9; c++)
		{
			if (bitvalue & this.notations[row][c]) positions |= (1 << c);
		}
		return positions;
	},

	setPositionsInRow : function (bitvalue, row, positions)
	{
		// loop thru rows
		for (var c = 0; c < 9; c++)
		{
			if ((1 << c) & positions) this.notations[row][c] |= bitvalue;
			else this.notations[row][c] &= ~bitvalue;
		}
	},

	// returns a position mask of the value's presence in the col. Least significant bit is cell 0.
	getPositionsInCol : function (bitvalue, col)
	{
		var positions = 0; // variable to return

		// loop thru columns
		for (var r = 0; r < 9; r++)
		{
			if (bitvalue & this.notations[r][col]) positions |= (1 << r);
		}
		return positions;
	},

	setPositionsInCol : function (bitvalue, col, positions)
	{
		// loop thru columns
		for (var r = 0; r < 9; r++)
		{
			if ((1 << r) & positions) this.notations[r][col] |= bitvalue;
			else this.notations[r][col] &= ~bitvalue;
		}
	},

	// returns a position mask of the value's presence in the box. Least significant bit is cell 0.
	getPositionsInBox : function (bitvalue, box)
	{
		var positions = 0; // variable to return
		var pbit = 1;

		var HomeRow = CalcBoxHomeCell(box);
		var HomeCol = (box % 3) * 3;

		// loop thru box
		for (var r = HomeRow; r < HomeRow + 3; r++)
		{
			for (var c = HomeCol; c < HomeCol + 3; c++)
			{
				if (bitvalue & this.notations[r][c]) positions |= pbit;
				pbit <<= 1;
			}
		}
		return positions;
	},

	setPositionsInBox : function (bitvalue, box, positions)
	{
		var pbit = 1;

		var HomeRow = CalcBoxHomeCell(box);
		var HomeCol = (box % 3) * 3;

		// loop thru box
		for (var r = HomeRow; r < HomeRow + 3; r++)
		{
			for (var c = HomeCol; c < HomeCol + 3; c++)
			{
				if (pbit & positions) this.notations[r][c] |= bitvalue;
				else this.notations[r][c] &= ~bitvalue;
				pbit <<= 1;
			}
		}
	},

	// a bunch of grid administration function.

	// populate notation grid with tallied candidates.
	populateNotations : function ()
	{
		for (var r = 0; r < 9; r++)
		{
			for (var c = 0; c < 9; c++)
			{
				if (this.isEmpty(r, c))
					this.notations[r][c] = this.tallyCandidates(r, c);
				else
					this.notations[r][c] = this.data[r][c];
			}
		}
	},

	resetNotations : function ()
	{
		for (var r = 0; r < 9; r++)
		{
			for (var c = 0; c < 9; c++)
			{
				if (this.isEmpty(r, c))
					this.notations[r][c] = 511;
				else
					this.notations[r][c] = this.data[r][c];
			}
		}
	},

	clearData : function ()
	{
		for (var r = 0; r < 9; r++)
		{
			this.data[r] = [0, 0, 0, 0, 0, 0, 0, 0, 0];
		}
		this.dataCount = 0;
	},

	// attempts to repopulate the Grid from a string. returns true if successful, false otherwise.
	loadFromString : function (input)
	{
		// if it is not a string longer than 81 characters, it will not successfully populate
		if (typeof(input) !== 'string' || input.length < 81) return false;

		// count the number filled cells
		var NumberCount = input.match(/\d/g).length;

		// in this basic format, the value count must be less than or equal to 81.
		if (NumberCount > 81) return false;

		// Now we need to find a character that has (81 - NumberCount) occurances. It will represent empty cells.
		if (NumberCount < 81)
		{
			var EmptyCellCount = 81 - NumberCount;
			var CharCode, RE;

			var NumbersStripped = input.replace(/\d/g, ''); // get everything that is not a number
			
			while (NumbersStripped)
			{
				// Cannot use the character directly because some characters can be interpreted as RegExp component

				// get the Unicode char code of character
				CharCode = NumbersStripped.charCodeAt(0).toString(16); 
				// pad it to 4 characters, some browser choke on it if we do \uFF instead of \uFFFF
				CharCode = '\\u0000'.substring(0, 6 - CharCode.length) + CharCode; 

				RE = new RegExp(CharCode, 'g'); // create RegEx from code

				if (NumbersStripped.match(RE).length === EmptyCellCount)
				{
					// Zero character is the first character of the current NumbersStripped.
					input = input.replace(RE, '0');
					break;
				}
				else
				{
					NumbersStripped = NumbersStripped.replace(RE, '');
				}
			}
		}

		input = input.replace(/\D/g, '');

		// if it is not a string with exactly 81 digits at this point, it will not successfully populate
		if (input.length !== 81) return false;

		var i = 0;
		for (var r = 0; r < 9; r++)
		{
			for (var c = 0; c < 9; c++)
			{
				this.setDigit(r, c, parseInt(input.charAt(i)));
				i++;
			}
		}
		this.populateNotations();
		return true;
	},

	toLocaleString : function ()
	{
		var s = '', digit;
		for (var r = 0; r < 9; r++)
		{
			if (r === 3 || r === 6)
				s += '-----------\n';
			for (var c = 0; c < 9; c++)
			{
				if (c === 3 || c === 6)
					s += '|';
				digit = this.getDigit(r, c);
				s += digit || '.';
			}
			s += '\n';
		}
		return s;
	},

	toString : function ()
	{
		var s = '';
		for (var r = 0; r < 9; r++)
			for (var c = 0; c < 9; c++)
				s += this.getDigit(r, c);

		return s;
	},

	candidateCount : function ()
	{
		var count = 0;
		for (var r = 0; r < 9; r++)
			for (var c = 0; c < 9; c++)
				count += this.notations[r][c].bitCount();

		return count;
	},

	// Check if the cell has conflict
	// expect the cell have value, and the digit is not in the candidates list
	cellValueHasConflict : function (row, col)
	{
		return (this.data[row][col] & this.tallyCandidates(row, col, true)) === 0;
	},

	// Check if the grid has conflicting cells
	gridHasConflict : function ()
	{
		for (var r = 0; r < 9; r++)
			for (var c = 0; c < 9; c++)
			{
				if (this.isEmpty(r, c))
				{
					if (this.tallyCandidates(r, c) === 0) return true;
				}
				else
				{
					if (this.cellValueHasConflict(r, c)) return true;
				}
			}
		return false;
	},

	// enforce a mask on the row, column, and box
	enforceMask : function (row, col, mask)
	{
		var func = function (grid, m) { return function (r, c) { grid.notations[r][c] &= m; }; } (this, mask);
		CallPeers (row, col, func);
	}
}

// loops a strategy function until solve or until no avail is returned.
SudokuGrid.prototype.solveLoop = function (StepSolver, arg)
{
	if (Function.prototype.call)
	{
		// var start = (new Date()).getTime()
		do
		{
			// var t = new Date();
			// arg(t.getTime() - start);
			if (!StepSolver.call(this, arg)) return false;
		} while (this.dataCount < 81)
		return true;
	}
	else
	{
		// var start = (new Date()).getTime()
		do
		{
			this.__temp__ = StepSolver;
			// var t = new Date();
			// arg(t.getTime() - start);
			if (!this.__temp__(arg)) return false;
		} while (this.dataCount < 81)
		delete this.__temp__;
		return true;
	}
}

// run thru all the strategy and returns true after the first strategy that has some effect
function LogicalSolveStep(LogFunc)
{
	// var start = (new Date()).getTime()
	var oldCount = this.dataCount;
	if (!LogFunc) LogFunc = function () {};

	if (this.strategySingles())
	{
		LogFunc('Singles [' + oldCount + '\u2192' + this.dataCount + ']');
		return true;
	}

	// Basic Strategies
	if (this.strategyHiddenSingles())
	{
		LogFunc('Hidden Singles [' + oldCount + '\u2192' + this.dataCount + ']');
		return true;
	}
	if (this.strategyLockedCandidates())
	{
		LogFunc('Locked Candidates');
		return true;
	}

	// Subset Strategies
	if (this.strategyNakedSubset())
	{
		LogFunc('Naked Subsets');
		return true;
	}
	if (this.strategyHiddenSubset())
	{
		LogFunc('Hidden Subsets');
		return true;
	}
	if (this.strategyFish())
	{
		LogFunc('X-Wing / N-Fish');
		return true;
	}

	// Chain Strategies
	if (this.strategyMultiColoring())
	{
		LogFunc('Multi-Coloring');
		return true;
	}

	if (this.strategyAPE())
	{
		LogFunc('Aligned Pair Exclusion');
		return true;
	}

	if (this.strategy3DMedusa())
	{
		LogFunc('3D Medusa');
		return true;
	}

/*	if (this.strategyTemplating())
	{
		LogFunc('Templating');
		return true;
	}*/

	return false;
}
